const
	MAXN = 10010;
	INF = round(1e9);

type
	edge = record
		a, b, cost : longint;
	end;

var
	e : array[0..MAXN] of edge;

procedure BellmanFord(v, t : longint);

var
	i, j, cur, cc, x, y, kk, tt : longint;
	d, p, path : array[0..MAXN] of longint;
	 
begin
	for i := 1 to MAXN do
		d[i] := INF;
	fillchar(p, sizeof(p), -1);
	d[v] := 0;
	x := -1;
	for i := 1 to n do begin
		x := -1;
		for j := 1 to m do
			if (d[e[j].a] < INF) and (d[e[j].b] > d[e[j].a] + e[j].cost) then begin
				d[e[j].b] := d[e[j].a] + e[j].cost;
				p[e[j].b] := e[j].a;
				x := e[j].b;
			end;
	end;
	if d[t] = INF then {no way from V to T} else begin
		cc := 0;    
		cur := t;
		while cur <> -1 do begin
			inc(cc);
			path[cc] := cur;
			cur := p[cur];	
		end;
		kk := cc shr 1;
		for i := 1 to kk do begin
			tt := path[i];
			path[i] := path[cc - i + 1];
			path[cc - i + 1] := tt;
		end;
	end;
	if x = -1 then {no negative cycle from V} else begin
		y := x;	
		for i := 1 to n do
			y := p[y]; 
		cc := 0;
		cur := y;
		while true do begin
			inc(cc);
			path[cc] := cur;
			if (cur = y) and (cc > 1) then break;
			cur := p[cur];
		end;
		kk := cc shr 1;
		for i := 1 to kk do begin
			tt := path[i];
			path[i] := path[cc - i + 1];
			path[cc - i + 1] := tt;
		end;
	end;
end;
